#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

#define NUM 1000 
//#define DEBUG

int main() {
    long* array = (long *)malloc(NUM * sizeof(long));
    long pivot;
    int i, j;
    clock_t start, end;
    double duration;

    srand(time(0));
    for (i = 0; i < NUM; ++i)
        array[i] = rand() % (10 * NUM);

#ifdef DEBUG
    for (i = 0; i < NUM; ++i)
        printf("%ld ", array[i]);
    printf("\n");
#endif

    start = clock();
    for (i = 1; i < NUM; ++i) {
        pivot = array[i];
        for (j = i - 1; j >= 0 && pivot < array[j]; --j) {
            array[j + 1] = array[j];
        }  
        if (pivot < array[j + 1])
            array[j + 1] = pivot;
    }
    end = clock();

#ifdef DEBUG
    for (i = 0; i < NUM; ++i)
        printf("%ld ", array[i]);
    printf("\n");
#endif

    duration = (double)(end - start);
    printf("%.8f\n", (duration / CLOCKS_PER_SEC));

    return 0;
}
